/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年10月11日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<vector<int>> res(m, vector<int>(n,0));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if( matrix[i][j] == 1 ){
                    res[i][j] = m + n;
                }

                if( i > 0 ){
                    res[i][j] = min(res[i-1][j]+1, res[i][j]);
                }
                if( j > 0 ){
                    res[i][j] = min(res[i][j-1]+1, res[i][j]);
                }
            }
        }

        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--){
                if( j < n - 1 ){
                    res[i][j] = min(res[i][j+1]+1, res[i][j]);
                }
                if( i < m - 1 ){
                    res[i][j] = min(res[i+1][j]+1, res[i][j]);
                }
            }
        }

        return res;
    }
};


class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<vector<int>> res(m, vector<int>(n,m+n));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    res[i][j] = 0;
                }else{
                    if(i > 0){
                        res[i][j] = min(res[i][j], res[i-1][j] + 1);
                    }

                    if(j > 0){
                        res[i][j] = min(res[i][j], res[i][j-1] + 1);
                    }
                }
            }
        }

        for(int i = m-1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--){
                if( i < m - 1){
                    res[i][j] = min(res[i][j], res[i+1][j] + 1);
                }
                if( j < n - 1 ){
                    res[i][j] = min(res[i][j], res[i][j+1] + 1);
                }
            }
        }

        return res;
    }
};

